# 《搜索插入位置》
# 原题链接：https://leetcode.cn/leetbook/read/array-and-string/cxqdh/

# 需求分析：
# 1、给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
# 2、如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
# 3、必须使用时间复杂度为 O(log n) 的算法。

# 示例 1:
# 输入: nums = [1, 3, 5, 6], target = 5
# 输出: 2

# 示例 2:
# 输入: nums = [1, 3, 5, 6], target = 2
# 输出: 1

# 示例 3:
# 输入: nums = [1, 3, 5, 6], target = 7
# 输出: 4

# 提示:
# 1 <= nums.length <= 104
# -104 <= nums[i] <= 104
# nums 为 无重复元素 的 升序 排列数组
# -104 <= target <= 104

# 思路1：暴力算法，分情况讨论，将target与nums[i]进行比较，共4种情况（i∈[0,n-1]）
# 1、target == nums[i] return i
#    即，目标值等于数组中某元素
# 2、target < nums[0] return 0
#    即，目标值小于数组所有元素
# 3、nums[i-1] < target < nums[i] return i
#    即，目标值插入数组中间位置
# 4、target > nums[n-1] return n
#    即，目标值大于数组所有元素
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        for i in range(len(nums)):
            if target == nums[i]:
                return i
            elif target < nums[i]:
                if i == 0:
                    return 0
                else:
                    return i
            else:
                continue
        return len(nums)
# 优化：{1,2,3}是可以合并的，因为不论数组中是否存在nums[i] = target 都会返回i
# 1、target <= nums[i]
#    return i 即，nums中有大于等于target的元素
# 2、target > nums[n-1]
#    return n 即，nums中所有元素都小于target
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        length = len(nums)
        for i in range(length):
            if target <= nums[i]:
                return i
        return length

# 思路2：二分查找，当数据量十分大时，可以大幅减少比较操作
# 1、通过与中值mid比较，确定target大致位置（在left还是right？）
# 2、每次比较后，范围缩小一半
# 3、直至最后，范围缩小到只有一个元素 nums[x]
# 4、若 target <= nums[x] return x
# 5、若 target > nums[x] return x+1
# 注意：变量选取、边界值确定、循环结束条件

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)-1
        while left < right:
            mid = (left+right) >> 1
            if target <= nums[mid]:right = mid
            else:left = mid+1
        return left if target <= nums[left] else left+1

# 二分查找，注释版
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        # 定义变量：left、right 记录左右两点，用于计算mid值，避免重复计算
        left, right = 0, len(nums)-1  # 初始化：left、right 使其指向数组头、尾
        # 定义循环条件：最初通常left<right，随着循环次数left增加，right减少，直至left=right，结束循环
        while left < right:
            # 定义并计算变量：mid用于与target值比较
            mid = (left+right) >> 1  # 初始化：mid 计算中值，用位运算替代除法运算，提高效率
            # 值判断1：确定target在left还是right 缩小范围
            if target <= nums[mid]: # 说明target可能在区间[left,mid]里
                right = mid
            else:                   # 说明target可能在区间(mid,right]里
                left = mid+1
        # 循环结束后left一定等于right，但mid还未计算，所以不能用mid
        if target <= nums[left]:
            return left
        else: 
            return left+1

# 二分查找：优化
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        
# 相关链接：
# 1、闭区间、左闭右开区间和开区间三种写法：https://leetcode.cn/problems/search-insert-position/solution/er-fen-cha-zhao-zong-shi-xie-bu-dui-yi-g-nq23/
# 2、左闭右开的统一习惯：https://www.zhihu.com/question/393142367
# 3、二分查找的通用模板写法：https://leetcode.cn/problems/search-insert-position/solution/shu-zu-zong-jie-liao-er-fen-cha-zhao-de-w61pe/
# 4、「代码随想录」带你学透二分法：https://leetcode.cn/problems/search-insert-position/solution/dai-ma-sui-xiang-lu-che-di-jiang-tou-er-5zs9r/
# 5、LeetCode官方解法：https://leetcode.cn/problems/search-insert-position/solution/sou-suo-cha-ru-wei-zhi-by-leetcode-solution/
# 6、一文带你搞定二分查找及其多个变种！：https://leetcode.cn/problems/search-insert-position/solution/yi-wen-dai-ni-gao-ding-er-fen-cha-zhao-j-69ao/

# 示例代码：
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)

        while left < right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid

        return left
